package com.camus.verify.biz.impl;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

import org.apache.commons.collections4.CollectionUtils;
import org.springframework.core.annotation.Order;
import org.springframework.stereotype.Service;

import com.camus.framework.common.CommonConstant;
import com.camus.utils.NumberUtils;
import com.camus.verify.algorithm.MatchTarget;
import com.camus.verify.algorithm.SubsetAlgorithmAssembler4BigDecimal;
import com.camus.verify.bo.MatchBO;
import com.camus.verify.bo.MatchParam;
import com.camus.verify.bo.TargetSumParam;
import com.camus.verify.entity.VerifyTask;
import com.camus.verify.entity.VerifyTaskAp;
import com.camus.verify.entity.VerifyTaskInvoice;
import com.google.common.collect.Lists;

import cn.hutool.json.JSONUtil;

/**
 * 发票与台账多对多匹配
 * 
 * @author jie.deng
 *
 */
@Service
@Order(value = 5)
public class Many2ManyMatchHandler extends AbstractMatchHandler {

	@Override
	public List<MatchBO> match(final VerifyTask task, final List<VerifyTaskInvoice> invoiceCandidateList,
			final List<VerifyTaskAp> apCandidateList) {
		// 结果列表
		List<MatchBO> resultList = new ArrayList<>();

		// 候选列表
		List<VerifyTaskInvoice> leftCandidateList = invoiceCandidateList.stream().filter(t -> t.getMatched() == 0)
				.collect(Collectors.toList());
		List<VerifyTaskAp> rightCandidateList = apCandidateList.stream().filter(t -> t.getMatched() == 0)
				.collect(Collectors.toList());
		if (CollectionUtils.isEmpty(leftCandidateList) || CollectionUtils.isEmpty(rightCandidateList)) {
			return resultList;
		}
		if (log.isInfoEnabled()) {
			log.info("多对多匹配,入参={}", JSONUtil.toJsonStr(MatchParam.of(task, leftCandidateList, rightCandidateList)));
		}
		List<MatchTarget> leftMatchTargetList = leftCandidateList.stream()
				.map(t -> new MatchTarget(t, t.getPendingVerifyAmt())).collect(Collectors.toList());

		// 第一轮
		resultList.addAll(matchBySlideWindow(task, leftMatchTargetList, rightCandidateList));

		// 第二轮
		resultList.addAll(matchByLoop(task,
				leftMatchTargetList.stream().map(t -> (VerifyTaskInvoice) t.getRef()).collect(Collectors.toList()),
				rightCandidateList));

		if (log.isInfoEnabled()) {
			log.info("多对多匹配,返回值={}", JSONUtil.toJsonStr(resultList));
		}
		return resultList;
	}

	/**
	 * 先用递归算法选择发票集合，然后匹配台账集合
	 * 
	 * @param task
	 * @param leftMatchTargetList
	 * @param rightCandidateList
	 * @return
	 */
	private List<MatchBO> matchByLoop(VerifyTask task, final List<VerifyTaskInvoice> invoiceCandidateList,
			final List<VerifyTaskAp> apCandidateList) {
		List<MatchBO> resultList = Lists.newArrayList();
		if (CollectionUtils.isEmpty(invoiceCandidateList) || CollectionUtils.isEmpty(apCandidateList)) {
			return resultList;
		}
		if (invoiceCandidateList.size() <= apCandidateList.size()) {
			List<MatchTarget> leftMatchTargetList = invoiceCandidateList.stream()
					.map(t -> new MatchTarget(t, t.getPendingVerifyAmt())).collect(Collectors.toList());
			List<VerifyTaskAp> rightCandidateList = new ArrayList<>(apCandidateList);
			int len = leftMatchTargetList.size();
			Set<BigDecimal> unMatchedTargetSet = new HashSet<>();
			// 复杂度是2的n次方
			for (long i = 1; i < (long) Math.pow(2, len); i++) {
				// 特殊情况下的剪枝-左边已全部匹配
				if (leftMatchTargetList.stream().allMatch(t -> BigDecimal.ZERO.compareTo(t.getTarget()) == 0)) {
					break;
				}

				// 选择多个发票
				boolean[] flagArr = NumberUtils.toBoolArr(i, len);
				List<MatchTarget> leftChosenList = new ArrayList<>();
				for (int j = 0; j < len; j++) {
					if (flagArr[j]) {
						leftChosenList.add(leftMatchTargetList.get(j));
					}
				}
				BigDecimal target = leftChosenList.stream().map(MatchTarget::getTarget).reduce(BigDecimal.ZERO,
						BigDecimal::add);
				if (unMatchedTargetSet.contains(target)) {
					continue;
				}
				// 根据选择的多个发票，匹配选择多个台账
				SubsetAlgorithmAssembler4BigDecimal<VerifyTaskAp> subsetAssembler = new SubsetAlgorithmAssembler4BigDecimal<>();
				List<VerifyTaskAp> rightChosenList = subsetAssembler.findSubset(rightCandidateList,
						VerifyTaskAp::getPendingVerifyAmt, target, tolerance);
				// 组装匹配结果
				if (CollectionUtils.isNotEmpty(rightChosenList)) {
					// 组装匹配结果
					resultList.add(buildResultBO(task, leftChosenList.stream().map(t -> (VerifyTaskInvoice) t.getRef())
							.collect(Collectors.toList()), rightChosenList));
					// 变更循环变量
					rightCandidateList.removeAll(rightChosenList);
					for (MatchTarget leftCandidate : leftChosenList) {
						leftCandidate.setTarget(BigDecimal.ZERO);
					}
					// 特殊情况下的剪枝-台账已全部匹配
					if (CollectionUtils.isEmpty(rightCandidateList)) {
						break;
					}
				} else {
					unMatchedTargetSet.add(target);
				}
			}
		} else {
			List<MatchTarget> leftMatchTargetList = apCandidateList.stream()
					.map(t -> new MatchTarget(t, t.getPendingVerifyAmt())).collect(Collectors.toList());
			List<VerifyTaskInvoice> rightCandidateList = new ArrayList<>(invoiceCandidateList);
			int len = leftMatchTargetList.size();
			Set<BigDecimal> unMatchedTargetSet = new HashSet<>();
			// 复杂度是2的n次方
			for (long i = 1; (long) i < Math.pow(2, len); i++) {
				// 特殊情况下的剪枝-左边已全部匹配
				if (leftMatchTargetList.stream().allMatch(t -> BigDecimal.ZERO.compareTo(t.getTarget()) == 0)) {
					break;
				}
				// 选择多个台账
				boolean[] flagArr = NumberUtils.toBoolArr(i, len);
				List<MatchTarget> leftChosenList = new ArrayList<>();
				for (int j = 0; j < len; j++) {
					if (flagArr[j]) {
						leftChosenList.add(leftMatchTargetList.get(j));
					}
				}
				BigDecimal target = leftChosenList.stream().map(MatchTarget::getTarget).reduce(BigDecimal.ZERO,
						BigDecimal::add);
				if (unMatchedTargetSet.contains(target)) {
					continue;
				}
				// 根据选择的多个台账，匹配选择多个发票
				SubsetAlgorithmAssembler4BigDecimal<VerifyTaskInvoice> subsetAssembler = new SubsetAlgorithmAssembler4BigDecimal<>();
				List<VerifyTaskInvoice> rightChosenList = subsetAssembler.findSubset(rightCandidateList,
						VerifyTaskInvoice::getPendingVerifyAmt, target, tolerance);
				// 组装匹配结果
				if (CollectionUtils.isNotEmpty(rightChosenList)) {
					// 组装匹配结果
					resultList.add(buildResultBO(task, rightChosenList,
							leftChosenList.stream().map(t -> (VerifyTaskAp) t.getRef()).collect(Collectors.toList())));
					// 变更循环变量
					rightCandidateList.removeAll(rightChosenList);
					for (MatchTarget leftCandidate : leftChosenList) {
						leftCandidate.setTarget(BigDecimal.ZERO);
					}
					// 特殊情况下的剪枝-台账已全部匹配
					if (CollectionUtils.isEmpty(rightCandidateList)) {
						break;
					}
				} else {
					unMatchedTargetSet.add(target);
				}
			}
		}
		return resultList;
	}

	/**
	 * 先用滑动窗口算法选择发票集合，然后匹配台账集合
	 * 
	 * WARNING:如果匹配成功，会改变入参leftMatchTargetList 和 rightCandidateList 集合里元素的个数
	 * 
	 * @param task
	 * @param leftMatchTargetList
	 * @param rightCandidateList
	 * @return
	 */
	private List<MatchBO> matchBySlideWindow(final VerifyTask task, List<MatchTarget> leftMatchTargetList,
			List<VerifyTaskAp> rightCandidateList) {
		List<MatchBO> resultList = Lists.newArrayList();
		if (CollectionUtils.isEmpty(leftMatchTargetList) || CollectionUtils.isEmpty(rightCandidateList)) {
			return resultList;
		}

		BigDecimal[] prefixSumArr = calPrefixSumArr(leftMatchTargetList);
		int len = leftMatchTargetList.size();
		Set<BigDecimal> unMatchedTargetSet = new HashSet<>();

		// 滑动窗口大小为2...len
		loop: for (int winSize = 2; winSize <= len; winSize++) {
			// 特殊情况下的剪枝-发票已全部匹配
			if (leftMatchTargetList.stream().allMatch(t -> BigDecimal.ZERO.compareTo(t.getTarget()) == 0)) {
				break;
			}
			// 区间和[i,j] = prefixSum[j] - prefixSum[i-1]
			for (int startIdx = 0, endIdx = startIdx + winSize - 1; endIdx < len; startIdx++, endIdx++) {
				// 选择多个发票
				// 求区间和[startIdx,endIdx]
				BigDecimal target = prefixSumArr[endIdx];
				if (startIdx > 0) {
					target = target.subtract(prefixSumArr[startIdx - 1]);
				}

				List<MatchTarget> leftChosenList = new ArrayList<>();
				for (int i = 0; i < winSize; i++) {
					MatchTarget item = leftMatchTargetList.get(i + startIdx);
					if (BigDecimal.ZERO.compareTo(item.getTarget()) != 0) {
						leftChosenList.add(item);
					}
				}
				if (CollectionUtils.isEmpty(leftChosenList) || unMatchedTargetSet.contains(target)) {
					continue;
				}

				// 根据选择的多个发票，匹配选择多个台账
				SubsetAlgorithmAssembler4BigDecimal<VerifyTaskAp> subsetAssembler = new SubsetAlgorithmAssembler4BigDecimal<>();
				List<VerifyTaskAp> rightChosenList = subsetAssembler.findSubset(rightCandidateList,
						VerifyTaskAp::getPendingVerifyAmt, target, tolerance);
				// 组装匹配结果
				if (CollectionUtils.isNotEmpty(rightChosenList)) {
					// 组装匹配结果
					resultList.add(buildResultBO(task, leftChosenList.stream().map(t -> (VerifyTaskInvoice) t.getRef())
							.collect(Collectors.toList()), rightChosenList));
					if (log.isDebugEnabled()) {
						log.debug("多对多匹配结果:" + CommonConstant.LOGGER_FORMATER_PARAM_RETURN,
								JSONUtil.toJsonStr(TargetSumParam.of(
										leftMatchTargetList.stream().map(MatchTarget::getTarget)
												.collect(Collectors.toList()),
										rightCandidateList.stream().map(VerifyTaskAp::getPendingVerifyAmt)
												.collect(Collectors.toList()),
										target, tolerance)),
								JSONUtil.toJsonStr(TargetSumParam.of(
										leftChosenList.stream().map(MatchTarget::getTarget)
												.collect(Collectors.toList()),
										rightChosenList.stream().map(VerifyTaskAp::getPendingVerifyAmt)
												.collect(Collectors.toList()),
										target, tolerance)));
					}
					// 变更循环变量
					rightCandidateList.removeAll(rightChosenList);
					for (MatchTarget leftCandidate : leftChosenList) {
						leftCandidate.setTarget(BigDecimal.ZERO);
						prefixSumArr = calPrefixSumArr(leftMatchTargetList);
					}
					// 特殊情况下的剪枝-台账已全部匹配
					if (CollectionUtils.isEmpty(rightCandidateList)) {
						break loop;
					}
				} else {
					unMatchedTargetSet.add(target);
				}
			}
		}

		if (resultList.size() > 0) {
			for (Iterator<MatchTarget> iterator = leftMatchTargetList.iterator(); iterator.hasNext();) {
				MatchTarget item = (MatchTarget) iterator.next();
				if (BigDecimal.ZERO.compareTo(item.getTarget()) == 0) {
					iterator.remove();
				}
			}
		}

		return resultList;
	}

	private BigDecimal[] calPrefixSumArr(List<MatchTarget> leftMatchTargetList) {
		int len = leftMatchTargetList.size();
		// 前缀和
		BigDecimal[] prefixSumArr = new BigDecimal[len];
		prefixSumArr[0] = leftMatchTargetList.get(0).getTarget();
		for (int i = 1; i < len; i++) {
			prefixSumArr[i] = prefixSumArr[i - 1].add(leftMatchTargetList.get(i).getTarget());
		}
		return prefixSumArr;
	}

	@Override
	public String getMatchHandlerName() {
		return "多对多匹配";
	}

}
